package com.dyz.leetcode._15_BFSAndDFS;


import java.util.*;

public class _994_orangesRotting {
    //多元广度优先遍历
    private int[][] dirs = {{-1, 0},{1, 0},{0, -1},{0, 1}}; //左边 右边 上边 下边
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Map<String, Integer> map = new HashMap<>();
        Queue<int[]> queue = new ArrayDeque<>();
        //找到腐烂的🍊
        for (int row=0; row<rows; row++){
            for(int col=0; col<cols;col++){
                if(grid[row][col]==2){
                    int [] tmp = new int[]{row, col};
                    queue.offer(tmp);
                    map.put(Arrays.toString(tmp), 0);
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()){
            int[] curr = queue.poll();
            for(int[] dir:dirs){
                int nextRow = curr[0] + dir[0];
                int nextCol = curr[1] + dir[1];
                if(nextRow>=0 && nextRow<rows && nextCol>=0 && nextCol<cols && grid[nextRow][nextCol]==1){
                    grid[nextRow][nextCol] = 2;
                    int[] tmp = new int[]{nextRow, nextCol};
                    queue.offer(tmp);
                    //更新层信息, 上一层+1
                    int level = map.get(Arrays.toString(curr))+1;
                    map.put(Arrays.toString(tmp), level);
                    ans = level;
                }
            }
        }
        //遍历最后一边，还有新鲜🍊返回-1
        for (int row=0; row<rows; row++){
            for(int col=0; col<cols;col++){
                if(grid[row][col]==1){
                    return -1;
                }
             }
        }
       return ans;
    }

    public static void main(String[] args) {
        new _994_orangesRotting().orangesRotting(new int[][] {{2,1,1},{1,1,0},{0,1,1}});
    }
}
